package com.yaoli.base;

/**
 * Created by YaoLi on 2017/8/20.
 */
public class DuiSort {
    public static void main(String[] args) {
        //int [] array = {12,23,34,1,21};
        int [] array = {5 ,23,34,2,32,12,1,12,4,23,245,13};

        //      50,         0
        //     10,90,       1
        //  30,70, 40,80,   3   5
        // 60,20            7

        DuiSort duiSort = new DuiSort();
        duiSort.sort(array);


        //调整为一个大顶堆


    }

    public void sort(int array[]){
        //从最后一个非叶子结点开始调整位置
        for(int i = (array.length - 2 ) / 2; i >= 0 ; i--){
            adjust(array,i ,array.length);
        }//已经调整完毕，是个大顶堆

        //交换 排序
        for(int i = array.length - 1 ; i >= 0 ; i--){

            //每次交换，只要交换第一个和最后一个
            swap(array,0,i);

            //这里的 length 是不断减少的。
            adjust(array,0, i);

//            for(int j = (i - 1) / 2 ; j >= 0 ; j--){
//
//                adjust(array,j , i);
//
//            }
        }

        System.out.println("");
    }

    public void swap(int array [], int a ,int b){
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

    public void adjust(int array [],int p ,int length){

        //i = 0
        //i = 0 , 1
        //i = 1 , 3
        //i = 2 , 5

        //      50,         0
        //     10,90,       1
        //  30,70, 40,80,   3   5

        for(int parentPosition = p ; parentPosition < length ; ){
            //以下四行 找出 i 结点的，左结点大 还是 右边的结点的数值大
            int childPosition = 2 * parentPosition + 1;
            if(2*(parentPosition+1) < length && array[2*parentPosition + 1] < array[2*(parentPosition+1)]){
                childPosition = 2*(parentPosition+1);
            }

            //如果子节点的值大于父节点的值,就将子节点与父节点 交换位置
            if(childPosition < length && parentPosition < length && array[childPosition] > array[parentPosition]){
                int tmp = array[parentPosition];
                array[parentPosition] = array[childPosition];
                array[childPosition] = tmp;

                //孩子几点晋升为父节点
                parentPosition = childPosition;
            }else{
                break;
            }
        }

    }


}
